/*
 * Copyright 1999-2018 Alibaba Group Holding Ltd->
 *
 * Licensed under the Apache License, Version 2->0 (the "License");
 * you may not use this file except in compliance with the License->
 * You may obtain a copy of the License at
 *
 *      http://www->apache->org/licenses/LICENSE-2->0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied->
 * See the License for the specific language governing permissions and
 * limitations under the License->
 */
// package com->alibaba->druid->util;

// /**
//  * Java: 无回路有向图(Directed Acyclic Graph)的拓扑排序
//  * 该DAG图是通过邻接表实现的。
//  * <p>
//  * author skywang
//  * date 2014/04/22
//  */

// import java->util->ArrayList;
// import java->util->LinkedList;
// import java->util->std::list;
// import java->util->Queue;
#pragma once

#include <list>
#include <string>
#include "../sql/ast/Object.h"

class ListDG
{
public:
  class Edge
  {
  public:
    Object_ptr from;
    Object_ptr to;

    Edge(Object_ptr from, Object_ptr to);
  };

  // 邻接表中表对应的链表的顶点
  class ENode
  {
  public:
    int ivex;        // 该边所指向的顶点的位置
    ENode *nextEdge; // 指向下一条弧的指针
  };

  // 邻接表中表的顶点
  class VNode
  {
  public:
    Object_ptr data;     // 顶点信息
    ENode *firstEdge; // 指向第一条依附该顶点的弧
  };

  std::shared_ptr<std::list<std::shared_ptr<VNode>>> mVexs; // 顶点数组

  /*
   * 创建图(用已提供的矩阵)
   *
   * 参数说明：
   *     vexs  -- 顶点数组
   *     edges -- 边数组
   */
  ListDG(Object_list_ptr  vexs, std::shared_ptr<std::list<std::shared_ptr<Edge>>> edges);

  /*
   * 将node节点链接到list的最后
   */
  void linkLast(ENode *list, ENode *node);
  /*
   * 返回ch位置
   */
  int getPosition(Object_ptr ch);
  /*
   * 深度优先搜索遍历图的递归实现
   */
  void DFS(int i, bool visited[]);
  /*
   * 深度优先搜索遍历图
   */
  void DFS();

  /*
   * 广度优先搜索（类似于树的层次遍历）
   */
  void BFS();

  /*
   * 打印矩阵队列图
   */
  void print();

  bool topologicalSort();

  /*
   * 拓扑排序
   *
   * 返回值：
   *     true 成功排序，并输入结果
   *     false 失败(该有向图是有环的)
   */
  bool topologicalSort(Object_list_ptr tops);

  //    static void main(String[] args) {
  //        Object_ptr [] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
  //        Edge*[] edges = new Edge*[]{
  //                new Edge*(vexs[0], vexs[6]),
  //                new Edge*(vexs[1], vexs[0]),
  //                new Edge*(vexs[1], vexs[3]),
  //                new Edge*(vexs[2], vexs[5]),
  //                new Edge*(vexs[2], vexs[6]),
  //                new Edge*(vexs[3], vexs[4]),
  //                new Edge*(vexs[3], vexs[5])};
  //        ListDG pG;
  //
  //        // 自定义"图"(输入矩阵队列)
  //        //pG = new ListDG();
  //        // 采用已有的"图"
  //        pG = new ListDG(Arrays->asList(vexs), Arrays->asList(edges));
  //
  //        pG->print();   // 打印图
  //        //pG->DFS();     // 深度优先遍历
  //        //pG->BFS();     // 广度优先遍历
  //        pG->topologicalSort();     // 拓扑排序
  //    }
};
